import java.util.*;

class Solution1 {
    private boolean[][] vis;

    public void solve(char[][] board) {
        int n = board.length, m = board[0].length;
        vis = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][m - 1] == 'O') {
                bfs(board, i, m - 1);
            }
        }
        for (int i = 0; i < m; i++) {
            if (board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if (board[n - 1][i] == 'O') {
                bfs(board, n - 1, i);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && vis[i][j] == false) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void bfs(char[][] board, int i, int j) {
        Queue<Integer> qx = new LinkedList<>();
        Queue<Integer> qy = new LinkedList<>();
        int[] xx = {1, 0, -1, 0};
        int[] yy = {0, -1, 0, 1};
        int n = board.length, m = board[0].length;
        qx.add(i);
        qy.add(j);
        while (!qx.isEmpty()) {
            int x = qx.poll(), y = qy.poll();
            vis[x][y] = true;
            for (int k = 0; k < 4; k++) {
                int a = x + xx[k], b = y + yy[k];
                if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && board[a][b] == 'O') {
                    qx.add(a);
                    qy.add(b);
                    vis[a][b] = true;
                }
            }

            //System.out.println(qx.size());
        }
    }
}

class Solution2 {
    public int nearestExit(char[][] maze, int[] entrance) {
        int n = maze.length, m = maze[0].length;
        int x = entrance[0], y = entrance[1];
        Queue<Integer> qx = new LinkedList<>();
        Queue<Integer> qy = new LinkedList<>();
        boolean[][] vis = new boolean[n][m];
        vis[x][y] = true;
        int count = 0;
        int[] xx = {1, 0, -1, 0};
        int[] yy = {0, -1, 0, 1};
        qx.add(x);
        qy.add(y);
        while (!qx.isEmpty()) {
            x = qx.poll();
            y = qy.poll();
            int sz = qx.size();
            count++;
            for (int j = 0; j < sz; j++) {
                for (int i = 0; i < 4; i++) {
                    int a = x + xx[i], b = y + yy[i];
                    if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && maze[a][b] == '.') {
                        if (a == 0 || a == n - 1 || b == 0 || b == m - 1) return count;
                        qx.add(a);
                        qy.add(b);
                        vis[a][b] = true;
                    }
                }
            }
        }
        return -1;
    }
}

class Solution3 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        HashSet<String> hashBank = new HashSet<>();
        HashSet<String> vis = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        vis.add(startGene);
        for (String str : bank) {
            hashBank.add(str);
        }

        if (startGene.equals(endGene)) return 0;
        if (!hashBank.contains(endGene)) return -1;

        int count = 0;
        char[] changes = {'A', 'C', 'T', 'G'};
        while (!queue.isEmpty()) {
            int sz = queue.size();
            count++;
            for (int j = 0; j < sz; j++) {
                String str = queue.poll();
                for (int i = 0; i < 8; i++) {
                    char[] tmp = str.toCharArray();
                    for (int k = 0; k < 4; k++) {
                        tmp[i] = changes[k];
                        String next = new String(tmp);
                        if (!vis.contains(next) && hashBank.contains(next)) {
                            if (next.equals(endGene)) return count;
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

class Solution4 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) return 0;
        HashSet<String> hash = new HashSet<>();
        HashSet<String> vis = new HashSet<>();
        for (String str : wordList) {
            hash.add(str);
        }
        if (!hash.contains(endWord)) return 0;
        vis.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        int step = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            step++;
            while (sz-- > 0) {
                String str = queue.poll();
                for (int i = 0; i < str.length(); i++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        char[] tmp = str.toCharArray();
                        tmp[i] = ch;
                        String next = new String(tmp);
                        if (!vis.contains(next) && hash.contains(next)) {
                            if (next.equals(endWord)) return step + 1;
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}

class Solution {
    public int cutOffTree(List<List<Integer>> forest) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (List<Integer> list : forest) {
            for (int x : list) {
                if (x > 1) {
                    queue.add(x);
                }
            }
        }
        int n = forest.size(), m = forest.get(0).size();

        Queue<Integer> qx = new LinkedList<>();
        Queue<Integer> qy = new LinkedList<>();
        qx.add(0);
        qy.add(0);
        int[] xx = {1, 0, -1, 0};
        int[] yy = {0, 1, 0, -1};
        int step = 0;
        while(!queue.isEmpty()) {
            int target = queue.poll();
            int flag = 0;
            // bfs
            boolean[][] vis = new boolean[n][m];
            int count = 0;
            while (!qx.isEmpty()) {
                int sz = qx.size();
                count++;
                while (sz-- > 0) {
                    int x = qx.poll(), y = qy.poll();
                    if(forest.get(x).get(y) == target) {
                        flag = 1;
                        qx.add(x);
                        qy.add(y);
                        count--;
                        break;
                    }
                    vis[x][y] = true;
                    for (int i = 0; i < 4; i++) {
                        int dx = x + xx[i];
                        int dy = y + yy[i];
                        if (dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && forest.get(dx).get(dy) != 0) {
                            if(forest.get(dx).get(dy) == target) {
                                qx.clear();
                                qy.clear();
                                qx.add(dx);
                                qy.add(dy);
                                flag = 1;
                                break;
                            }else {
                                vis[dx][dy] = true;
                                qx.add(dx);
                                qy.add(dy);
                            }
                        }
                    }
                    if(flag == 1) break;
                }
                if(flag == 1) break;
            }
            if(flag == 0) {
                System.out.println(target);
                return -1;
            }
            step+= count;
        }
        return step;
    }
}

public class Test {
    public static void main(String[] args) {
        int a;
        char[][] map = {{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}};
        int ret = new Solution2().nearestExit(map, new int[]{1, 0});
        System.out.println(ret);
    }
}
